﻿// ***********************************************************************
// Assembly         : AgoritmoLibrary
// Author           : André Casaca
// Created          : 05-28-2013
//
// Last Modified By : André Casaca
// Last Modified On : 06-08-2013
// ***********************************************************************
// <copyright file="AlgoritmoLibery.cs" company="">
//     Copyright (c) . All rights reserved.
// </copyright>
// <summary></summary>
// ***********************************************************************
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using System.Threading.Tasks;
using NUnit.Framework;

namespace AgoritmoLibrary
{
    /// <summary>
    /// Sort.
    /// </summary>
    /// <remarks>Andre, 10/06/2013.</remarks>
    public class Sort
    {
        /// <summary>
        /// Executa o algoritmo InsertionSort
        /// </summary>
        /// <param name="A">Lista a Ordenar</param>
        /// <returns>Lista Ordenada</returns>
        public List<int> InsertionSort(List<int> A)
        {
            for (int j = 1; j < A.Count; j++)
            {
                int key = A[j];
                int i = j - 1;
                while (i > -1 && A[i] > key)
                {
                    A[i + 1] = A[i];
                    i -= 1;
                }
                A[i + 1] = key;
            }
            return A;
        }

        /// <summary>
        /// Executa o Algoritmo BubbleSort e ordena a Lista de Inteiros
        /// </summary>
        /// <param name="A">Lista a Ordenar</param>
        /// <returns>Lista Ordenada</returns>
        public List<int> BubbleSort(List<int> A)
        {
            for (int i = 0; i <= A.Count - 1; i++)
            {
                for (int j = A.Count - 1; j >= i + 1; j--)
                {
                    if (A[j] < A[j - 1])
                    {
                        int temp = A[j];
                        A[j] = A[j - 1];
                        A[j - 1] = temp;
                    }
                }
            }
            return A;
        }

        /// <summary>
        /// Executa o Algoritmo HeapSort e ordena a lista
        /// </summary>
        /// <param name="A">Lista a Ordenar</param>
        /// <returns>Lista Ordenada</returns>
        public List<int> HeapSort(List<int> A)
        {
            int heapSize = A.Count - 1;
            A = this.BuildMaxHeap(A, heapSize);
            for (int i = A.Count - 1; i >= 1; i--)
            {
                A = this.MaxHeapify(A, 0, heapSize);
                int temp = A[0];
                A[0] = A[i];
                A[i] = temp;
                heapSize -= 1;
                A = this.MaxHeapify(A, 0, heapSize);
            }
            return A;
        }

        /// <summary>
        /// Detecta o maior numero para o fim da Heap
        /// </summary>
        /// <param name="A">Lista a ser Ordenda</param>
        /// <param name="heapSize">O comprimento actual da Heap</param>
        /// <returns>A lista atual</returns>
        protected List<int> BuildMaxHeap(List<int> A, int heapSize)
        {
            for (int i = (int)Math.Floor(heapSize / 2.0); i >= 0; i--)
            {
                A = MaxHeapify(A, i, heapSize);
            }
            return A;
        }

        /// <summary>
        /// Passa o maior valor para o fim da Heap
        /// </summary>
        /// <param name="A">Lista a ser Ordenada</param>
        /// <param name="i">O index da Arvore para o calculo dos Ramos</param>
        /// <param name="heapSize">Tamanho da Heap</param>
        /// <returns>List{System.Int32}.</returns>
        protected List<int> MaxHeapify(List<int> A, int i, int heapSize)
        {
            int largest;
            int l = (2 * i) + 1;
            int r = (2 * i) + 2;

            if (l <= heapSize && A[l] > A[i])
            {
                largest = l;
            }
            else
            {
                largest = i;
            }
            if (r <= heapSize && A[r] > A[largest])
            {
                largest = r;
            }
            if (largest != i)
            {
                int temp = A[i];
                A[i] = A[largest];
                A[largest] = temp;
                this.MaxHeapify(A, largest, heapSize);
            }
            return A;
        }

        /// <summary>
        /// algoritmo Merge - Ordena parcialmente a Lista divindido-a em duas
        /// </summary>
        /// <param name="A">Lista a ser ordenada</param>
        /// <param name="p">Principio da lista</param>
        /// <param name="q">Onde dividir a lista</param>
        /// <param name="r">Fim da lista</param>
        /// <returns>List{System.Int32}.</returns>
        protected List<int> Merge(List<int> A, int p, int q, int r)
        {
            int n1 = q - p + 1;
            int n2 = r - q;
            List<int> L = new List<int>();
            List<int> R = new List<int>();
            int i;
            int j;
            for (i = 0; i < n1; i++)
            {
                L.Add(A[p + i]);
            }

            for (j = 0; j < n2; j++)
            {
                R.Add(A[q + j + 1]);
            }

            L.Add(9999);
            R.Add(9999);

            i = 0;
            j = 0;

            for (int k = p; k < r+1; k++)
            {
                if (L[i] <= R[j])
                {
                    A[k] = L[i];
                    i += 1;
                }
                else
                {
                    A[k] = R[j];
                    j += 1;
                }
            }
            return A;
        }

        /// <summary>
        /// Algoritmo MergeSort - Ordena a lista Completamente
        /// </summary>
        /// <param name="A">Lista a Ordenar</param>
        /// <param name="p">Index onde Começa a Ordenar</param>
        /// <param name="r">Index onde Termina de Ordenar</param>
        /// <returns>Lista Ordenada/Lista PArcialmente Ordenada</returns>
        public List<int> MergeSort(List<int> A, int p, int r)
        {
            if (p < r)
            {
                int q = (int)Math.Floor(((double)p + (double)r)/2.0);
                A = this.MergeSort(A, p, q);
                A = this.MergeSort(A, q + 1, r);
                A = this.Merge(A, p, q, r);
            }
            return A;
        }

        /// <summary>
        /// Algoritmo QuickSort - Ordena a Lista
        /// </summary>
        /// <param name="A">Lista a Ordenar</param>
        /// <param name="p">Index Onde Começa a Ordenar</param>
        /// <param name="r">Index onde termina de Ordenar</param>
        /// <returns>Lista Ordenada/Parcialmente Ordenada</returns>
        public List<int> QuickSort(List<int> A, int p, int r)
        {
            if (p < r)
            {
                int q = this.Partition(A, p, r);
                A = this.QuickSort(A, p, q - 1);
                A = this.QuickSort(A, q + 1, r);
            }
            return A;
        }

        /// <summary>
        /// Algoritmo PArtition - Ajuda o QuikSort a ordenar a lista apartir de um ramo
        /// </summary>
        /// <param name="A">Lista a Ordenar</param>
        /// <param name="p">index até Ordenar</param>
        /// <param name="r">Index do Ramo Pivot</param>
        /// <returns>System.Int32.</returns>
        protected int Partition(List<int> A, int p, int r)
        {
            int x = A[r];
            int i = p - 1;

            for (int y = p; y <= r - 1; y++)
            {
                if (A[y] <= x)
                {
                    i = i + 1;
                    int temp = A[i];
                    A[i] = A[y];
                    A[y] = temp;
                }
            }
            int temp2 = A[i + 1];
            A[i + 1] = A[r];
            A[r] = temp2;
            return i + 1;
        }

        /// <summary>
        /// Methodo de Teste do DLL
        /// </summary>
        [Test]
        public void NUnitTest(){
            List<int> lista = new List<int>{2, 5, 8, 9, 10, 3, 1, 11};
            Assert.AreEqual(this.BubbleSort(lista), new List<int> { 1, 2, 3, 5, 8, 9, 10, 11});
            Assert.AreEqual(this.MergeSort(lista, 0, 7), new List<int> { 1, 2, 3, 5, 8, 9, 10, 11 });
            Assert.AreEqual(this.InsertionSort(lista), new List<int> { 1, 2, 3, 5, 8, 9, 10, 11 });
            Assert.AreEqual(this.QuickSort(lista, 0, 7), new List<int> { 1, 2, 3, 5, 8, 9, 10, 11 });
            Assert.AreEqual(this.HeapSort(lista), new List<int> { 1, 2, 3, 5, 8, 9, 10, 11 });
        }
    }
}
